package q437_pathSum;

import CommonClass.Common.TreeNode;

import java.util.HashMap;
import java.util.Map;
public class Solution_2 {
    Map<Integer, Integer> prefixMap;
    int target;
    /*
    如果使用前缀和 实际上跟之前所学习的hash表来解决列表查询问题非常相似
    也就是每次遍历到一个节点的时候 查询之前有没有存储一个curSum - target的值的entry 如果有 则代表前面有一条路径加上这个节点可以满足一个答案
     */
    public int pathSum(TreeNode root, int sum) {
        prefixMap = new HashMap<>();
        target = sum;

        prefixMap.put(0, 1);
        return recur(root, 0);
    }

    private int recur(TreeNode node, int curSum) {
        if(node == null) {
            return 0;
        }

        int res = 0;
        curSum += node.val;

        res += prefixMap.getOrDefault(curSum - target, 0);
        prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) + 1);

        int left = recur(node.left, curSum);
        int right = recur(node.right, curSum);

        res = res + left + right;

        prefixMap.put(curSum, prefixMap.get(curSum) - 1);

        return res;
    }
}

